package com.explorati.LeetCode111.MinimumDepthOfBinaryTree;

/**
 * 111. Minimum Depth of Binary Tree
 * 
 * num不能为全局变量，需重写一个函数并将num当参数传入
 * 
 * The minimum depth is the number of nodes along the shortest path from the
 * root node down to the nearest leaf node.
 * 
 * @author explorati
 *
 */
public class Solution {
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public static int minDepth(TreeNode root) {
		if (root == null) {
			return 0;
		}
		// int l = 1 + minDepth(root.left);
		// int r = 1 + minDepth(root.right);
		// if (root.left == null) {
		// return r;
		// }
		// if (root.right == null) {
		// return l;
		// }
		// return Math.min(l, r);
		int num = 1;

		return minDepth(root, num);
	}

	public static int minDepth(TreeNode root, int num) {
		if (root.left == null && root.right == null) {
			return num;
		}
		if (root.left == null && root.right != null) {
			return minDepth(root.right, num + 1);
		} else if (root.right == null && root.left != null) {
			return minDepth(root.left, num + 1);
		} else {
			return Math.min(minDepth(root.left, num + 1), minDepth(root.right, num + 1));
		}
	}

	public static void main(String[] args) {
		Solution s = new Solution();
		TreeNode root = s.new TreeNode(1);
		root.left = s.new TreeNode(2);
		root.right = s.new TreeNode(3);
		root.left.left = s.new TreeNode(4);
		root.left.right = s.new TreeNode(5);

		int minDepth = minDepth(root);
		System.out.println(minDepth);
	}

}
